Path computation for tunnels of a computer network, e.g., label switched paths (LSPs), is generally performed in a distributed manner, where each head-end node of the tunnels computes paths for its tunnels independently from head-end nodes of other tunnels. For example, tunnels in many Multi-Protocol Label Switching (MPLS) Traffic Engineering (TE) networks (e.g., MPLS TE-LSPs) are computed using a distributed constrained shortest path first (CSPF) algorithm. As those skilled in the art will understand, distributed CSPF offers high flexibility/scalability, and is well-equipped to handle frequent topology changes, dynamic traffic demands, and resource availability changes.
One problem associated with distributed path computation is that while it may be highly flexible/scalable, it may be inefficient for optimizing tunnel placement within the network, i.e., due to the lack of path computation coordination among the head-end nodes. In particular, when one or more established tunnels utilize a link that becomes unavailable to those tunnels (e.g., due to failure of the link or preemption of certain tunnels on the link for a higher priority tunnel), each of the head-end nodes corresponding to the affected tunnels generally attempt to reroute the tunnels through the network. The distributed rerouting of the tunnels may cause a burst of signaling within the network to reroute the tunnels, which may lead to signaling failures, as will be understood by those skilled in the art. Also, “preemption cascading,” where one tunnel is rerouted and then preempts shortly thereafter a lower priority tunnel, which then preempts a still lower priority tunnel, etc., may occur with distributed rerouting of tunnels. In addition, if many smaller tunnels are rerouted throughout the network, those smaller tunnels may “fragment” the remaining bandwidth of the network, to the extent that even if a large amount of bandwidth is available from a source to a destination, that bandwidth may be fragmented into smaller amounts along multiple paths such that no one (acceptable) path exists upon which a large tunnel may be placed.
Further, when there is a link (or node) failure within a network, the total available bandwidth of the network is reduced. For instance, this may result in some tunnels that had been in place before the link failure not being able to find a path after the failure due to insufficient bandwidth availability of the network. For guaranteed traffic over the tunnels (e.g., voice, video, etc.), the tunnels that are able to find a suitable path may maintain the bandwidth guarantee, while other tunnels are not able to find a path, thus are unable to maintain their guarantee.
Due to the distributed nature of path computation for tunnels (e.g., distributed CSPF), it has generally not been possible to coordinate the rerouting (replacement) of tunnels in a computer network such that substantially all tunnels can be placed. In other words, it has generally not been possible to coordinate the timing, placement, and bandwidth reservation (e.g., fair bandwidth allocation) of tunnels using distributed path computation, particularly in the event of a link (or node) becoming unavailable to the tunnels, e.g., due to a failure or preemption on the link.